package shuati.chuanzhibei.chuanzhi24;

import java.util.Scanner;

/**
 * @author : LdLtd
 * @Date : 2024/12/21
 * @Description:
 * dd在玩跳格子游戏，具体游戏规则如下，
 * n个格子呈环形分布，顺时针方向分别标号为1~n，其中1和n相邻，
 * 每个格子上都有一个正整数ai，玩家可以选择一个点作为起点开始跳n下，
 * 第i次跳跃，玩家只可以选择当前位置左边或右边最近目尚未被跳跃过的位置进行一次跳跃，
 * 并获得i*a|p]的得分，其中p为第i次跳跃的位置。dd很鸡贼，想赢又不想动脑子，她希望你能给她规划路线以确保她的胜利
 *
 * 输入
 * 第1行1个数n(1≤ns2000)
 * 接下来一行n个数，表示a[i](1≤a[i]≤2000)
 *
 * 输出可以得到的最高分
 * 示例 1
 * 输入
 * 3
 * 1 1 1
 * 输出
 * 6
 * 说明
 * 可能方案
 * 1->2->3
 * 1->3->2
 * 2->1->3
 * 2->3->1
 * 3->1->2
 * 3->2->1
 * (以上数字表示格子标号)
 * 答案均为 1*1+2*1+3*1=6
 * 最优方案不唯一，最优答案唯一
 */
public class P6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取n
        int n = sc.nextInt();
        long[] a = new long[2 * n];

        // 读取a数组并填充环形数组
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            a[i + n] = a[i];
        }

        // 动态规划数组
        long[][] dp = new long[4200][4200];

        // 初始化dp数组
        for (int i = 1; i <= 2 * n - 1; i++) {
            //dp[i][i] = a[i] 表示单一格子的得分。dp[i][r] 用来表示从位置 i 到位置 r 跳跃时的最大得分。
            dp[i][i] = a[i - 1]; // 转换为0-based索引
        }

        // 进行动态规划计算
        //通过遍历子串长度 len，我们对于每一个子串 [l, r] 计算最大得分。每次可以选择从左端跳跃或者从右端跳跃，所以状态转移
        //dp[l][r] = Math.max(dp[l + 1][r] + a[l - 1] * len, dp[l][r - 1] + a[r - 1] * len);
        for (int len = 2; len <= n; len++) {
            for (int l = 1; l + len - 1 <= 2 * n - 1; l++) {
                int r = l + len - 1;
                dp[l][r] = Math.max(dp[l + 1][r] + a[l - 1] * len, dp[l][r - 1] + a[r - 1] * len);
            }
        }

        // 计算结果
        long ans = Long.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dp[i][i + n - 1]);
        }

        // 输出结果
        System.out.println(ans);
    }
}
